package linkedList.排序链表;

//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
// 示例 1： 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 示例 2： 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 示例 3： 
//输入：head = []
//输出：[]
// 提示： 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// Related Topics 链表 双指针 分治 排序 归并排序 👍 2577 👎 0


import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 归并排序
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode ans = mergeSort(head);
        return ans;
    }

    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = findMid(head);
        ListNode midNext = mid.next;
        // 切断链表，左边一直往下查找
        mid.next = null;
        // 排序左边
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(midNext);
        return merge(l, r);
    }

    private ListNode merge(ListNode l, ListNode r) {
        ListNode ans = new ListNode(-1);
        ListNode cur = ans;
        while (l != null && r != null) {
            if (l.val > r.val) {
                cur.next = r;
                r = r.next;
            } else {
                cur.next = l;
                l = l.next;
            }
            cur = cur.next;
        }
        cur.next = l == null ? r : l;
        return ans.next;
    }

    public ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(5, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(1, new ListNode(0))))));
        Solution solution = new Solution();
        ListNode listNode = solution.sortList(head);
    }

}
